home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / archiver / lz13.zip / LZCOMP3.ASM < prev    next >
Assembly Source File  |  1988-10-20  |  8KB  |  318 lines
  1.     title    lzcomp - file compressor using limpel-ziv algorithm
  2.  
  3. ;Tom Pfau
  4. ;Digital Equipment Corporation
  5. ;Parsippany, NJ
  6. ;
  7. ;v1.2, Toad Hall Tweak
  8. ; - Converting to COM file.
  9. ; - Gonna use BP to hold bit_offset throughout (faster)
  10. ; - Moved most buffers outside code space.
  11. ; - Now accepts input file on command line, otherwise inputs
  12. ;   from StdIn
  13. ; - Always outputs to StdOut
  14. ; Nuts .. StdIn doesn't seem to work .. donno why.
  15. ; Won't work as a filter either (which I had hoped for).
  16. ; WILL take cmd line file name, redirect it appropriately.
  17. ;
  18. ;David Kirschbaum
  19. ;Toad Hall
  20. ;kirsch@braggvax.ARPA
  21.  
  22. ;Constants
  23. CLEAR        equ    256        ;Clear code
  24. EOF        equ    257        ;End of file marker
  25. FIRST_FREE    equ    258        ;First free code
  26. MAXMAX        equ    4096        ;Max code + 1
  27. BUFFSIZE    EQU    4096        ;TH read/write buffers
  28.     include macros2.mlb
  29.  
  30. ;Hash table entry
  31. hash_rec    struc
  32. first    dw    ?            ; First entry with this value
  33. next    dw    ?            ; Next entry along chain
  34. char    db    ?            ; Suffix char
  35. hash_rec    ends
  36.  
  37. ;Declare Segments
  38. Code    segment para public 'code'
  39.     assume    CS:Code, DS:Code, ES:Code
  40.  
  41.     org    100H
  42.  
  43. LzComp    proc    near
  44.     jmp    Start
  45.  
  46. ;TH collecting all data segment stuff
  47. input_handle    dw    0        ;default StdIn
  48. prefix_code    dw    0    ;?
  49. free_code    dw    0    ;?
  50. max_code    dw    0    ;?
  51. nbits        dw    0    ;?
  52. k        db    0    ;?
  53.  
  54. ;bit_offset    dw    0    ;?
  55. input_offset    dw    0
  56. input_size    dw    0
  57. LzComp    endp
  58.  
  59.  
  60. start    proc    near
  61. ;TH we won't mess with any memory allocating, since I think
  62. ;all required buffers, hash tables, etc. can work within
  63. ;a lousy 64Kb segment.
  64. ;Won't even bother moving the stackpointer for now either.
  65.  
  66.     mov    si,80H                ;point to PSP cmd line
  67.     lodsb                    ;snarf cmd line len byte
  68.     or    al,al                ;anything on cmd line?
  69.     jz    Start_Process            ;nope, use < stdin
  70.  
  71.     xor    ah,ah                ;clear msb
  72. ;SI now points to 81H
  73.     mov    dx,si                ;not quite first char
  74.     inc    dx                ;DX points to target filename
  75.     add    si,ax                ;point to beyond last char
  76.     mov    [si],ah                ;make file name AsciiZ
  77.     mov    ax,3D00H            ;open file/device
  78.     int    21H
  79.     jb    Terminate            ;failed somehow, die
  80.  
  81.     mov    input_handle,ax            ;save input handle
  82.  
  83. Start_Process:
  84.     call    compress        ;Compress file
  85. Terminate:
  86.     mov    ah,4CH            ;terminate, errorlevel in AL
  87.     int    21H
  88. start    endp
  89.  
  90. compress    proc    near
  91.  
  92. l1:    call    init_table        ;Initialize the table and some vars
  93.     mov    ax,CLEAR        ;Write a clear code
  94.     call    write_code
  95.     call    read_char        ;Read first char
  96.  
  97. l4:    xor    ah,ah            ;Turn char into code
  98. l4a:    mov    prefix_code,ax        ;Set prefix code
  99.     call    read_char        ;Read next char
  100.     jc    l17            ;Carry means EOF
  101.     mov    k,al            ;Save char in k
  102.     mov    bx,prefix_code        ;Get prefix code
  103.     call    lookup_code        ;See if this pair in table
  104.     jnc    l4a            ;nc means yes, new code in ax
  105.     call    add_code        ;Add pair to table
  106.     push    bx            ;Save new code
  107.     mov    ax,prefix_code        ;Write old prefix code
  108.     call    write_code
  109.     pop    bx
  110.     mov    al,k            ;Get last char
  111.     cmp    bx,max_code        ;Exceed code size?
  112.     jl    l4            ;less means no
  113.     cmp    nbits,12        ;Currently less than 12 bits?
  114.     jl    l14            ;yes
  115.      mov    ax,CLEAR        ;Write a clear code
  116.      call    write_code
  117.      call    init_table        ;Reinit table
  118.      mov    al,k            ;get last char
  119.      jmp    l4            ;Start over
  120.  
  121. l14:    inc    nbits            ;Increase number of bits
  122.     shl    max_code,1        ;Double max code size
  123.     jmp    l4            ;Get next char
  124.  
  125. l17:    mov    ax,prefix_code        ;Write last code
  126.     call    write_code
  127.     mov    ax,EOF            ;Write EOF code
  128.     call    write_code
  129.     mov    ax,bp    ;bit_offset    ;Make sure buffer is flushed to file
  130.     or    ax,ax            ;TH
  131.     je    l18
  132.      mov    cx,8            ;convert bits to bytes
  133.      xor    dx,dx
  134.      div    cx
  135.      or    dx,dx            ;If extra bits, make sure they get
  136.      je    l17a            ;written
  137.       inc    ax
  138. l17a:     call    flush
  139. l18:    ret
  140. compress    endp
  141.  
  142. init_table    proc    near
  143.     mov    nbits,9            ;Set code size to 9
  144.     mov    max_code,512        ;Set max code to 512
  145.  
  146.     mov    ax,-1            ;Unused flag
  147.     mov    cx,640            ;Clear first 256 entries
  148.     mov    di,offset hash        ;TH Point to first entry
  149. rep    stosw                ;Clear it out
  150.     mov    free_code,FIRST_FREE    ;Set next code to use
  151.     ret                ;done
  152. init_table    endp
  153.  
  154. write_code    proc    near
  155.     push    ax            ;Save code
  156.     mov    ax,bp    ;bit_offset    ;Get bit offset
  157. ;TH we're keeping bit_offset in BP
  158. ;    mov    cx,nbits        ;Adjust bit offset by code size
  159. ;    add    bit_offset,cx
  160.     add    bp,nbits        ;TH adjust bit offset by code size
  161.     mov    cx,8            ;Convert bit offset to byte offset
  162.     xor    dx,dx
  163.     div    cx
  164. ;    cmp    ax,1020            ;Approaching end of buffer?
  165.     cmp    ax,BUFFSIZE-4        ;TH approaching end of buffer?
  166.     jl    wc1            ;less means no
  167.      call    flush            ;Write the buffer
  168. ;TH we're keeping bit_offset in BP
  169. ;     push    dx            ;dx contains offset within byte
  170. ;     add    dx,nbits        ;adjust by code size
  171. ;     mov    bit_offset,dx        ;new bit offset
  172. ;     pop    dx            ;restore dx
  173.      mov    bp,dx            ;TH dx contains offset within byte
  174.      add    bp,nbits        ;TH adjust by code size
  175.  
  176.      add    ax,offset output_data    ;Point to last byte
  177.      mov    si,ax            ;put in si
  178.      mov    al,[si]            ;move byte to first position
  179.      mov    byte ptr output_data,al
  180.      xor    ax,ax            ;Byte offset of zero
  181. wc1:    add    ax,offset output_data    ;Point into buffer
  182.     mov    di,ax            ;Destination
  183.     pop    ax            ;Restore code
  184.     mov    cx,dx            ;offset within byte
  185.     xor    dx,dx            ;dx will catch bits rotated out
  186.     jcxz    wc3            ;If offset in byte is zero, skip shift
  187. wc2:     shl    ax,1            ;Rotate code
  188.      rcl    dx,1
  189.      loop    wc2
  190.      or    al,[di]            ;Grab bits currently in buffer
  191. wc3:    stosw                ;Save data
  192.     mov    al,dl            ;Grab extra bits
  193.     stosb                ;and save
  194.     ret
  195. write_code    endp
  196.  
  197.  
  198. flush        proc    near
  199.     push    ax            ;Save all registers
  200.     push    dx
  201.     mov    dx,offset output_data    ;buffer to write
  202.     mov    cx,ax            ;AX contains number of bytes to write
  203.     mov    bx,1            ;StdOut
  204.     mov    ah,40H            ;write to file/device
  205.     int    21H
  206.     pop    dx
  207.     pop    ax
  208.     jb    File_Error        ;failed somehow
  209.     ret
  210. flush        endp
  211.  
  212. read_char    proc    near
  213.     mov    di,input_offset        ;Anything left in buffer?
  214.     cmp    di,input_size
  215.     jl    rd1            ;less means yes
  216.  
  217.     mov    dx,offset input_data    ;buffer to read into
  218.     mov    bx,input_handle        ;input handle
  219. ;    mov    cx,1024            ;read this many bytes
  220.     mov    cx,BUFFSIZE        ;TH read this many bytes
  221.     mov    ah,3FH            ;read from file/device
  222.     int    21H
  223.     jb    File_Error        ;failed somehow, die
  224.     or    ax,ax            ;anything read?
  225.     jz    rd2            ;nope, we're finished
  226.  
  227.     mov    input_size,ax        ;Save bytes read
  228.     xor    di,di            ;TH clear DI
  229.     mov    input_offset,di    ;TH 0    ;Point to beginning of buffer
  230. rd1:
  231. ;TH the mov/add instrs below are faster than the LEA.
  232. ;    lea    si,input_data[di]    ;Point at character
  233.     mov    si,offset input_data    ;TH
  234.     add    si,di            ;Point at char
  235.     lodsb                ;Read it in
  236.     inc    input_offset        ;Adjust pointer
  237.     clc                ;Success
  238.     ret
  239.  
  240. rd2:    stc                ;Nothing left
  241.     ret
  242.  
  243. File_Error:
  244.     jmp    Terminate        ;File error, terminate
  245.                     ;errorlevel in AL
  246. read_char    endp
  247.  
  248.  
  249. lookup_code    proc    near
  250.     call    index            ;convert code to address
  251.     xor    di,di    ;TH         ;flag
  252.     cmp    [si].first,-1        ;Has this code been used?
  253.     je    gc4            ;equal means no
  254.  
  255.     inc    di            ;set flag
  256.     mov    bx,[si].first        ;Get first entry
  257. gc2:    call    index            ;convert code to address
  258.     cmp    [si].char,al        ;is char the same?
  259.     jne    gc3            ;ne means no
  260.      clc                ;success
  261.      mov    ax,bx            ;put found code in ax
  262.      ret                ;done
  263.  
  264. gc3:    cmp    [si].next,-1        ;More left with this prefix?
  265.     je    gc4            ;equal means no
  266.      mov    bx,[si].next        ;get next code
  267.      jmp    gc2            ;try again
  268.  
  269. gc4:    stc                ;not found
  270.     ret                ;done
  271. lookup_code    endp
  272.  
  273.  
  274. index        proc    near
  275.     mov    si,bx            ;si = bx * 5 (5 byte hash entries)
  276.     shl    si,1            ;si = bx * 2 * 2 + bx
  277.     shl    si,1
  278.     add    si,bx
  279.     add    si,offset hash        ;TH plus hash table base
  280.     ret
  281. index        endp
  282.  
  283. add_code    proc    near
  284. ;Only called once
  285.     mov    bx,free_code        ;Get code to use
  286.     or    di,di    ;TH        ;First use of this prefix?
  287.     je    ac1            ;equal means yes
  288.      mov    [si].next,bx        ;point last use to new entry
  289.      jmp    short ac2
  290.  
  291. ac1:    mov    [si].first,bx        ;Point first use to new entry
  292. ac2:    cmp    bx,MAXMAX        ;Have we reached code limit?
  293.     je    ac3            ;equal means yes, just return
  294.      call    index            ;get address of new entry
  295. ;TH switched around a little
  296.      mov    [si].char,al        ;save suffix char
  297.      mov    ax,-1            ;TH do this once (ok to destroy AX)
  298.      mov    [si].first,ax    ;-1    ;initialize pointers
  299.      mov    [si].next,ax    ;-1
  300.      inc    free_code        ;TH adjust next code
  301. ac3:    ret
  302. add_code    endp
  303.  
  304. ;TH input/output buffers moved here outside code space
  305.     even
  306.  
  307. output_data    equ    $            ;db    1024 dup (?)
  308. input_data    equ    output_data+BUFFSIZE    ;db    1024 dup (?)
  309.  
  310. ;Instead of using a separ